Date modified: Mon 2023-05-15 . 09:27 AM
Date created: Sat 2023-10-07 . 09:02 PM
# Three-page embedding of graphs and knots. (I'll have to revisit this) A classic question to ask about a graph is whether it can be drawn (embedded) on a plane without intersecting itself. Such a graph is called **planar graph**. As we know, not all graphs are planar, and by Kuratowski theorem we know that a graph is planar if and only if it contains a subgraph that is a copy of $K_5$ or $K_{3,3}$ (or some subdivision of them). A natural generalization of planarity is to ask can a graph be embededded (where edges don't intersect) in a **book** of $k$-many pages, which is $k$ many half-planes all glued at their common boundary, forming the **seam** or spine of the book. In this $k$-page book world, the seam is where one can travel between the pages. (Note each page has both sides the same, there is no double sided-ness.)![[---images/Three page embedding of graphs and knots 2023-05-05 15.44.05.excalidraw.svg]]%%[[---images/Three page embedding of graphs and knots 2023-05-05 15.44.05.excalidraw|🖋 Edit in Excalidraw]], and the [[Excalidraw/Three page embedding of graphs and knots 2023-05-05 15.44.05.excalidraw.dark.svg|dark exported image]]%% So the natural question to ask is: When can a graph be embedded in some $k$-page book, for some $k$? As it turns out, **every graph can be embedded in a $3$-page book !** And similarly, **every knot and link can be embedded in a $3$-page book** as well! (At least, when the graph and knot are "finite" enough.) For example, can you find a 3-page embedding of the Hopf link? ![[---images/Three page embedding of graphs and knots 2023-05-05 16.00.20.excalidraw.svg]] %%[[---images/Three page embedding of graphs and knots 2023-05-05 16.00.20.excalidraw|🖋 Edit in Excalidraw]], and the [[Excalidraw/Three page embedding of graphs and knots 2023-05-05 16.00.20.excalidraw.dark.svg|dark exported image]]%% Or the $K_{3,3}$ graph? ![[---images/Three page embedding of graphs and knots 2023-05-05 17.26.04.excalidraw.svg]] %%[[---images/Three page embedding of graphs and knots 2023-05-05 17.26.04.excalidraw|🖋 Edit in Excalidraw]], and the [[Excalidraw/Three page embedding of graphs and knots 2023-05-05 17.26.04.excalidraw.dark.svg|dark exported image]]%%That is, draw them on a 3-page book without self-intersections. --- This task may at first look impossible, as intuitively each circles occupy a plane, and one may think this needs 4 pages. But let us look at how we may handle the intersections:![[---images/Three page embedding of graphs and knots 2023-05-05 16.31.12.excalidraw.svg]]%%[[---images/Three page embedding of graphs and knots 2023-05-05 16.31.12.excalidraw|🖋 Edit in Excalidraw]], and the [[Excalidraw/Three page embedding of graphs and knots 2023-05-05 16.31.12.excalidraw.dark.svg|dark exported image]]%% Whenever there is an apparent intersection in a plane projection, we can build a bridge to pass through the crossing. And all we need to do is to make the bridge to start ane end on the seam and live in the third page. Here is a nicer rendering of this 3-page embedding for the Hopf link:![[---images/Three page embedding of graphs and knots 2023-05-05 16.39.53.excalidraw.svg]]%%[[---images/Three page embedding of graphs and knots 2023-05-05 16.39.53.excalidraw|🖋 Edit in Excalidraw]], and the [[Excalidraw/Three page embedding of graphs and knots 2023-05-05 16.39.53.excalidraw.dark.svg|dark exported image]]%% As for $K_{3,3}$, note we can first choose a projection of this graph ![[---images/Three page embedding of graphs and knots 2023-05-05 17.28.48.excalidraw.svg]] %%[[---images/Three page embedding of graphs and knots 2023-05-05 17.28.48.excalidraw|🖋 Edit in Excalidraw]], and the [[Excalidraw/Three page embedding of graphs and knots 2023-05-05 17.28.48.excalidraw.dark.svg|dark exported image]]%% --- So this is our strategy. First project the graph or link onto the plane, and build a bridge to cross over any intersection. Now we just need to make all these bridges occur at the seam and live on the third page. To do this, we can first draw a curve that threads through the intersections, and then deform the graph or link so that the thread is straight. Then do the lifting of the bridges into the third page! For example, the Borromean ring: ![[---images/Three page embedding of graphs and knots 2023-05-05 17.56.06.excalidraw.svg]] %%[[---images/Three page embedding of graphs and knots 2023-05-05 17.56.06.excalidraw|🖋 Edit in Excalidraw]], and the [[Excalidraw/Three page embedding of graphs and knots 2023-05-05 17.56.06.excalidraw.dark.svg|dark exported image]]%% --- What if the graph is infinite? Such as $K(\mathbb Z)$ ? Or even $K(\mathbb R)$? Our contruction above depends on a finiteness of how each edge intersects.... And in the case of graphs, what if we also require the vertices to all be on the seam / spine? #graph-theory #knot-theory